The present invention relates to apparatus and methods for electronically performing a Fourier analysis of a two dimensional image. Its capabilities are useful in the fields of processing radar or optical images for bandwidth reduction, digital pattern recognition, image enhancement, etc.
The present device operates in two dimensions in that there are two waves present in the input signal, and two Fourier transformations are performed.
The Fourier integral can be used to calculate the frequency spectrum of an amplitude-time wave form. The Fourier integral for a voltage signal v(t) may be expressed as ##EQU1## WHERE J=.sqroot.-1 AND W IS FREQUENCY IN RADIANS PER SEC. F(w) is also known as the frequency spectrum of the signal v(t), which is represented as the amplitude of each frequency component plotted vs. frequency. It may be thought of as the breaking down of a complex wave form into sine waves present in different amounts of various discrete frequencies. The input wave is said to be plotted in the time domain while the analyzed wave is plotted in the frequency domain. A two dimensional Fourier transform is expressed as a double integral, one integral being performed in each dimension.
A typical prior art device applies an input wave form to an analog multiplier. A sine wave whose frequency can be varied linearly is then multiplied with the input to be analyzed. The multiplier output is filtered so that a dc voltage is obtained whenever the sine wave frequency reaches the fundamental or a harmonic of the wave form to be analyzed.
For two dimensional data, a software algorithm must be employed with the above technique.
A coherent optical method has also been developed for use with two dimensional data. An input signal is used to modulate a light beam in accordance with its amplitude to create a photographic record. The film is then illuminated by a laser and the image focused through a "transform lens" well known in the optical arts. Basically, the device uses optical and mechanical means to convert a signal from the time domain to the frequency domain.
Both of these approaches have drawbacks. The digital approach is either very slow if carried out by conventional minicomputers, or very expensive, if carried out by hardwire processors. Additionally, with the Fast Fourier Transform (FFT) computer algorithm there is no means for obtaining anything less than the complete Fourier transform. If only a few of the Fourier components are required for a given application, the complete calculation of the whole Fourier transform must be carried out anyway. The optical approach requires a transparent replica of the image to be transformed. To date, this requirement has excluded the optical processors from real-time, or even near real-time applications. Also, although it is relatively simple to obtain the power spectrum of an image with optical means, the true Fourier transform (i.e. including negative components) is more difficult to produce as the optics required must be very stable.
The present invention makes use of the fact that the correlation function is mathematically related to the Fourier transform, eq. (1): ##EQU2## where cc.sub.ab is the correlation function of the two signals a(t) and b(t) and .tau. is their relative displacement.
When a(t) and b(t) are different signals, the operation is termed "cross correlation." The function is at a maximum when the two signals are identical. Numerous correlation devices exist for the comparison of an input signal with one or more stored signals.
A correlation device generates a pattern that is a time averaged or integrated product of two complete signals as their relative displacement is shifted. Minicomputers are used to perform this function, but hardware devices are available which employ sophisticated digitizing circuits and circulating memories to store the reference signal. When sampling techniques are employed, equations (1) and (2) are written as sums of terms.
Two dimensional correlators have recently been developed. Bromley et al. in U.S. Pat. No. 3,937,942 describe a device wherein a light source is modulated by an input signal and illuminates a mask whose opacity varies according to several reference signals disposed in bands on the mask. A multi-element, multi-channel charge coupled device then receives light transmitted through the mask so that each reference portion of the mask falls on a different channel. The charge picked up by each element is proportional to the correlation between the light source signal and the corresponding mask portion. The signal clocked out from each channel is a correlation function for a particular reference signal. The device of Bromley et al. of course can not be considered truly two-dimensional because there is only one input signal but devices with two light sources can readily be envisioned.
Powers et al. in U.S. Pat. No. 3,842,251 describe a correlator in which the input is two dimensional information in the form of a phased or "chirped" radar return signal, this signal being characterized as in the nature of a hologram. The input modulates the write beam of a storage tube. A storage tube is an electron tube into which information can be introduced by a writing beam onto a storage grid, from which the information is later extracted by a reading beam. (See Storage Tubes and Their Basic Principles by M. Knoll and B. Kazan, John Wiley & Sons, 1952). The read beam of the tube is modulated with a reference holographic image in the form of an electron mask. When scanning the stored image under these conditions, at any given point on the grid, output is obtained only when the stored and input images overlap.